<?php
/*
 * 假设所有的图形都在第一象限内，
 * rectangles = [
 *   [1,1,3,3],
 *   [3,1,4,2],
 *   [3,2,4,4],
 *   [1,3,2,4],
 *   [2,3,3,4]
 * ]
 * 其中，[1,1,3,3]表示第1个矩形左上角的坐标为(1,1)，右下角的坐标为(3,3)
 * [3,1,4,2]表示第2个矩形左上角的坐标为(3,1)，右下角的坐标为(4,2)...
 * 按照这种方法可以给你几组矩形，请判断他们能不能正好组成一个完整的大矩形，且没有重合的部分。
 * 完整描述：搜perfect rectangle
 */

require_once '../../../class/HashSet.class.php';
$rectangles = [
   [1,1,3,3],
   [3,1,4,2],
   [3,2,4,4],
   [1,3,2,4],
   [2,3,3,4]
 ];
$obj = new Code_04_PerfectRectangle();
$res = $obj->main($rectangles);
var_dump($res);

class Code_04_PerfectRectangle
{
    // 如果严丝合缝的话，除了最外圈的矩形的四个顶点只出现一次，其他所有的点都出现过偶数次
    public function main($rectangles)
    {
        $set = new HashSet();
        $area = 0;
        $xL = PHP_INT_MAX;          //x最左
        $xR = PHP_INT_MIN;          //x最右
        $yD = PHP_INT_MAX;          //y最上
        $yU = PHP_INT_MIN;          //y最下
        foreach ($rectangles as $rect) {
            // rect[0] 左下角点x坐标
            // rect[1] 左下角点y坐标
            // rect[2] 右上角点x坐标
            // rect[3] 右上角点y坐标
            $xL = min($rect[0], $xL);
            $yD = min($rect[1], $yD);
            $xR = max($rect[2], $xR);
            $yU = max($rect[3], $yU);
            $area += ($rect[2] - $rect[0]) * ($rect[3] - $rect[1]);  // 所有小矩形面积的累加和
            $s1 = $rect[0] . '_' . $rect[1];        //左下角点坐标
            $s2 = $rect[0] . '_' . $rect[3];        //左上角点坐标
            $s3 = $rect[2] . '_' . $rect[3];        //右上角点坐标
            $s4 = $rect[2] . '_' . $rect[1];        //右下角点坐标
            // 之前加过返回false，没加过返回true
            if (!$set->put($s1)) $set->remove($s1);
            if (!$set->put($s2)) $set->remove($s2);
            if (!$set->put($s3)) $set->remove($s3);
            if (!$set->put($s4)) $set->remove($s4);
        }
        // set中应该只有四个顶点
        if (!$set->contains($xL . "_" . $yD) || !$set->contains($xL . "_" . $yU)
            || !$set->contains($xR . "_" . $yD) || !$set->contains($xR . "_" . $yU)
            || $set->size() != 4) {
            return false;
        }
        // 整个大矩形的面积应该等于所有小矩形的和
        return $area == ($xR - $xL) * ($yU - $yD);

    }

}